package leetcode.calc._06_07;

import org.springframework.util.Assert;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 * <p>
 * 输入：n = 1
 * 输出：["()"]
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 8
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/generate-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _07_03_022_括号生成 {
    public static void main(String[] args) {
        Solution sol = new _07_03_022_括号生成().new Solution();

        String str = "()((()))()";
        int index = 0;
        while ((index = str.indexOf("()", index)) != -1) {
            System.out.println(index);
            System.out.println(str.substring(0, index) + "(())" + str.substring(index + 2));
            index++;
        }

        if (true) {
            int param = 3;
            List<String> res = sol.generateParenthesis(param);
            String rel = "[((())), (()()), (())(), ()(()), ()()()]";
            Assert.isTrue(rel.equals(res.toString()), String.format("\n%s !=\n%s", res , rel));
        }
        if (true) {
            int param = 1;
            List<String> res = sol.generateParenthesis(param);
            String rel = "[()]";
            Assert.isTrue(rel.equals(res.toString()), String.format("\n%s !=\n%s", res , rel));
        }
        if (true) {
            int param = 4;
            List<String> res = sol.generateParenthesis(param);
            String rel = "[(((()))), ((()())), ((())()), ((()))(), (()(())), (()()()), (()())(), (())(()), (())()(), ()((())), ()(()()), ()(())(), ()()(()), ()()()()]";
            Assert.isTrue(rel.equals(res.toString()), String.format("\n%s !=\n%s", res , rel));
        }
        if (true) {
            int param = 6;
            List<String> res = sol.generateParenthesis(param);
            String rel = "[(((((()))))), ((((()())))), ((((())()))), ((((()))())), ((((())))()), ((((()))))(), (((()(())))), (((()()()))), (((()())())), (((()()))()), (((()())))(), (((())(()))), (((())()())), (((())())()), (((())()))(), (((()))(())), (((()))()()), (((()))())(), (((())))(()), (((())))()(), ((()((())))), ((()(()()))), ((()(())())), ((()(()))()), ((()(())))(), ((()()(()))), ((()()()())), ((()()())()), ((()()()))(), ((()())(())), ((()())()()), ((()())())(), ((()()))(()), ((()()))()(), ((())((()))), ((())(()())), ((())(())()), ((())(()))(), ((())()(())), ((())()()()), ((())()())(), ((())())(()), ((())())()(), ((()))((())), ((()))(()()), ((()))(())(), ((()))()(()), ((()))()()(), (()(((())))), (()((()()))), (()((())())), (()((()))()), (()((())))(), (()(()(()))), (()(()()())), (()(()())()), (()(()()))(), (()(())(())), (()(())()()), (()(())())(), (()(()))(()), (()(()))()(), (()()((()))), (()()(()())), (()()(())()), (()()(()))(), (()()()(...";
            Assert.isTrue(rel.equals(res.toString()), String.format("\n%s !=\n%s", res , rel));
        }
    }
    class Solution {
        public List<String> generateParenthesis(int num) {
            // 递归组合
            ArrayList<String> list = new ArrayList<>();
            LinkedList<Node> nodes = new LinkedList<>();
            nodes.add(new Node(num));
            while (!nodes.isEmpty()) {
                Node node = nodes.remove();
                Node newNode = node.add();
                if (newNode != null) {
                    nodes.add(node);
                    nodes.add(newNode);
                    continue;
                }
                if (node.isDone()) {
                    list.add(node.str);
                } else {
                    nodes.add(node);
                }
            }
            return list;
        }


        class Node {
            int left;
            int right;
            String str = "(";
            public Node(int len) {
                this.left = len - 1;
                this.right = len;
            }

            public Node(int left, int right, String str) {
                this.left = left;
                this.right = right;
                this.str = str;
            }

            public Node add() {
                Node node = null;
                if (left == 0) {
                    right--;
                    str += ")";
                }
                else if (left < right) {
                    node = new Node(left, right - 1, str + ")");
                    str += "(";
                    left--;
                } else  {
                    str += "(";
                    left--;
                }
                return node;
            }
            public boolean isDone() {
                return left == 0 && right == 0;
            }
        }
    }
    
}
